package com.lry.basic.algorithm.stack;

import java.util.Stack;
//https://leetcode-cn.com/problems/sum-of-subarray-minimums/submissions/
class SubarrayMins {

    public static void main(String[] args) {
        System.out.println(sumSubarrayMins(new int[]{3, 1, 2, 4}));
    }
     public static int sumSubarrayMins(int[] arr) {
        int [] newarr = new int[arr.length+1];
        System.arraycopy(arr,0,newarr,0,arr.length);
        newarr[arr.length] = 0 ;

        long ans = 0;
        Stack<Integer> stack = new Stack();
        long mod = 1000000007;

        for(int i=0;i<newarr.length;i++){

            while(!stack.isEmpty()&&newarr[stack.peek()] >= newarr[i]){
                int index = stack.peek();
                stack.pop();

                int pre = -1;
                if(!stack.isEmpty()){
                    pre = stack.peek();
                }

                int m = index - pre -1;
                int n = i - index -1;

                ans += (long)newarr[index] *(m+1)*(n+1)%mod;
                ans %=mod;
            }
            stack.push(i);
        }


        return (int)(ans);
    }

    public static int sumSubarrayMins2(int[] arr) {
        int n = arr.length;
        int[] left = new int[n];//存储左边第一个小于当前值的下标
        Stack<Integer> stack = new Stack();
        for(int i=0;i<n;i++){
            while(!stack.isEmpty()&&arr[stack.peek()] > arr[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                left[i] = -1;
            }else{
                left[i] = stack.peek();
            }
            stack.push(i);
        }

        int[] right = new int[n];//存储右边第一个小于当前值的下标
        stack.clear();
        for(int i=n-1;i>=0;i--){
            while(!stack.isEmpty()&&arr[stack.peek()] >= arr[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                right[i] = n;
            }else{
                right[i] = stack.peek();
            }
            stack.push(i);
        }


        long ans = 0;

        for(int i=0;i<arr.length;i++){
            ans += (long)arr[i]*(i-left[i]-1+1)*(right[i]-i-1+1);
        }

        return (int)(ans % (1000000007));
    }
}